package com.hit.basmath.interview.we_meet.bytedance;

/**
 * 151. 翻转字符串里的单词
 * <p>
 * 给定一个字符串，逐个翻转字符串中的每个单词。
 * <p>
 * 说明：
 * <p>
 * 无空格字符构成一个 单词 。
 * 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 * 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 * <p>
 * 示例 1：
 * <p>
 * 输入："the sky is blue"
 * 输出："blue is sky the"
 * <p>
 * 示例 2：
 * <p>
 * 输入："  hello world!  "
 * 输出："world! hello"
 * 解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 * <p>
 * 示例 3：
 * <p>
 * 输入："a good   example"
 * 输出："example good a"
 * 解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 * <p>
 * 示例 4：
 * <p>
 * 输入：s = "  Bob    Loves  Alice   "
 * 输出："Alice Loves Bob"
 * <p>
 * 示例 5：
 * <p>
 * 输入：s = "Alice does not even like bob"
 * 输出："bob like even not does Alice"
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 10^4
 * s 包含英文大小写字母、数字和空格 ' '
 * s 中 至少存在一个 单词
 * <p>
 * 进阶：
 * <p>
 * 请尝试使用 O(1) 额外空间复杂度的原地解法。
 */
public class _151 {
    public String reverseWords(String s) {
        String[] parts = s.trim().split("\\s+");
        StringBuilder sb = new StringBuilder("");
        for (int i = parts.length - 1; i >= 0; i--) {
            sb.append(parts[i]).append(" ");
        }
        return sb.toString().trim();
    }

    public String reverseWords2(String s) {
        /**
         * reverse the whole string and convert to char array
         */
        char[] str = reverse(s.toCharArray(), 0, s.length() - 1);
        /**
         * start and end positions of a current word
         */
        int start = 0, end = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] != ' ') { //
                /**
                 * If the current char is letter,
                 * just move this letter to the next free pos
                 */
                str[end++] = str[i]; //
            } else if (i > 0 && str[i - 1] != ' ') {
                /**
                 * If the first space after word, reverse the word
                 */
                reverse(str, start, end - 1);
                str[end++] = ' '; // and put the space after it
                start = end; // move start position further for the next word
            }
        }
        reverse(str, start, end - 1); // reverse the tail word if it's there
        // here's an ugly return just because we need to return Java's String
        // also as there could be spaces at the end of original string
        // we need to consider redundant space we have put there before
        return new String(str, 0, end > 0 && str[end - 1] == ' ' ? end - 1 : end);
    }

    // reverses the part of an array and returns the input array for convenience
    private char[] reverse(char[] arr, int i, int j) {
        while (i < j) {
            char tmp = arr[i];
            arr[i++] = arr[j];
            arr[j--] = tmp;
        }
        return arr;
    }
}
